#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/4 22:21
# @USER    : Shengji He
# @File    : CourseSchedule.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from collections import defaultdict
from typing import List


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        """
        There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

        Some courses may have prerequisites, for example to take course 0 you have to first take course 1,
        which is expressed as a pair: [0,1]

        Given the total number of courses and a list of prerequisite pairs, is it possible for you
        to finish all courses?

        Example 1:
            Input: numCourses = 2, prerequisites = [[1,0]]

            Output: true

            Explanation: There are a total of 2 courses to take.
                         To take course 1 you should have finished course 0. So it is possible.
        Example 2:
            Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

            Output: false

            Explanation: There are a total of 2 courses to take.
                         To take course 1 you should have finished course 0, and to take course 0 you should
                         also have finished course 1. So it is impossible.


        Constraints:
            - The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
            - You may assume that there are no duplicate edges in the input prerequisites.
            - 1 <= numCourses <= 10^5

        :param numCourses:
        :param prerequisites:
        :return:
        """
        edges = defaultdict(list)
        visited = [0] * numCourses
        result = list()
        valid = True
        for info in prerequisites:
            edges[info[1]].append(info[0])

        def dfs(u: int):
            nonlocal valid
            visited[u] = 1
            for v in edges[u]:
                if visited[v] == 0:
                    dfs(v)
                    if not valid:
                        return
                elif visited[v] == 1:
                    valid = False
                    return
                else:
                    pass

            visited[u] = 2
            result.append(u)

        for i in range(numCourses):
            if valid and not visited[i]:
                dfs(i)
        return valid


if __name__ == '__main__':
    numCourses = 2
    prerequisites = [[1, 0], [0, 1]]
    # prerequisites = [[1, 0]]

    S = Solution()
    print(S.canFinish(numCourses, prerequisites))
    print('done')
